class UnionFind4:
    """
    数组的下标表示元素
    数组self.parent下标对应的值为元素对应的父节点
    如果父节点和元素一样那么该元素为单独的一个组
    根节点没有父节点 self.parent[p] == p
    """
    def __init__(self, n):
        self.count = n 
        self.parent = [0]*n
        # 初始：每个元素互不连接
        for i in range(n):
            self.parent[i] = i
        
        # self.sz[i]表示以i为根的集合中的元素个数
        # 一开始都是1
        # self.sz = [1] * n

        # self.rank[i]表示根节点为i的树的高度
        self.rank = [1]*n
    
    # 找到p对应的根节点
    def find(self, p):
        assert p >= 0 and p < self.count
        while p != self.parent[p]:
            p = self.parent[p]
        return p
    
    # 有相同的根
    def is_connected(self, p, q):
        return self.find(p) == self.find(q)

    # 元素的个数多的组，高度不一定就高 - 如： 一个根节点有多个叶子节点
    # 基于树的高度而不是元素个数进行合并更加合理
    def union(self, p, q):
        p_root = self.find(p)
        q_root = self.find(q)

        # 已经相连，什么也不做
        if p_root == q_root:
            return
        
        # p所在的组的高度小于q所在的组的高度
        if self.rank[p_root] < self.rank[q_root]:
            self.parent[p_root] = q_root
        elif self.rank[p_root] > self.rank[q_root]:
            self.parent[q_root] = p_root
        else:
            # self.parent[p_root] = q_root
            self.parent[q_root] = p_root
            self.rank[p_root] += 1
